package com.example.demo.leetcode.top;

import java.util.Arrays;

/**
 * @author xujimou
 * @date 2021/2/4 15:22
 **/
public class JuZheng_搜索矩阵 {


    static volatile boolean flag = false;

    public static boolean searchMatrix(int[][] matrix, int target) {
        int x =matrix.length/2;
        int y = matrix[0].length/2;
        int [][] arr = new int[matrix.length][matrix[0].length];
        dfs(matrix,arr,target,x,y);
        return flag;

    }


    public static void dfs(int[][] matrix,int [][]arr ,int target,int x,int y){

        if(x<0 || x>=matrix.length || y<0 || y>=matrix[0].length || arr[x][y]==1 || flag){
            return;
        }
        if(matrix[x][y]==target){
            flag = true;
            return;
        }
        arr[x][y]=1;
        if(matrix[x][y]<target){
            dfs(matrix,arr,target,x+1,y);
            dfs(matrix,arr,target,x,y+1);
        }else{
            dfs(matrix,arr,target,x-1,y);
            dfs(matrix,arr,target,x,y-1);
        }

    }

    public static void main(String[] args) {

        int [][] arr= {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(searchMatrix(arr,20));
    }

}
